﻿#include <iostream>
#include <stack>

using namespace std;

template<class T>
class GetMinValueStack
{
    typedef bool(*compare)(const T&, const T&);

public:
    void setCompareFunc(compare c);
    void push(T val);
    int pop();
    int getMin();

private:
    stack<T> iStack;
    stack<T> minStack;
    // 自定义比较器，需要外界传入
    compare compareFunc;
};

template<class T>
void GetMinValueStack<T>::setCompareFunc(compare c)
{
    compareFunc = c;
}

template<class T>
void GetMinValueStack<T>::push(T val)
{
    iStack.push(val);
    if (minStack.empty())
    {
        minStack.push(val);
    }
    else
    {
        T top = minStack.top();
        minStack.push(compareFunc(val, top) ? val : top);
    }
}

template<class T>
int GetMinValueStack<T>::pop()
{
    T top = iStack.top();
    iStack.pop();
    minStack.pop();
    return top;
}

template<class T>
int GetMinValueStack<T>::getMin()
{
    return minStack.top();
}

static bool compareInt(const int& a, const int& b)
{
    return a < b;
}

/**
 * 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
 * 要求：
 * 1. pop,push,getMin操作的时间复杂度都是O(1)
 * 2. 设计的栈类型可以使用现成的栈结构
 */
int main_GetMinValueStack()
{
    int numbers[] = {10,4,5,3,8,7,9,11,20,12,15};
    int size = sizeof(numbers) / sizeof(int);
    GetMinValueStack<int> stack;
    stack.setCompareFunc(compareInt);
    for (int i = 0; i < size; i++)
    {
        stack.push(numbers[i]);
    }

    for (int i = 0; i < size; i++)
    {
        int min = stack.getMin();
        int p = stack.pop();
        printf("%d:min=%d,top=%d\n", i, min, p);
    }

    return 0;
}